/**
 * 
 */
package sorting.passed2;

import java.util.Arrays;
import java.util.Comparator;

/**
Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.
 */
public class LargestNumber {

	
    public String largestNumber(int[] num) {
    	if (num == null || num.length == 0) {
    		return "";
    	}
    	Comparator<String> comp = new Comparator<String>(){
			@Override
			public int compare(String s1, String s2) {
				// pitfall s1 is head of s2 if s2 + s1 > s1 + s2
				final String str1 = s2 + s1;
				final String str2 = s1 + s2;
				
				return str1.compareTo(str2);
			}
    	};
    	
    	String[] numInStr = toStringArray(num);
    	Arrays.sort(numInStr, comp);
    	
    	//pitfall [0, 0] should return "0" instead of "00"
    	if (numInStr[0].charAt(0) == '0') {
    		return "0";
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	for (String s : numInStr) {
    		sb.append(s);
    	}
    	
    	return sb.toString();
    }
    
    private String[] toStringArray(int[] arr) {
    	assert(arr != null && arr.length > 0);
    	String[] result = new String[arr.length];
    	for (int i = 0, size = arr.length; i < size; i++) {
    		result[i] = String.valueOf(arr[i]);
    	}
    	return result;
    }
    
	
	/**
	 * 
	 */
	public LargestNumber() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
